package 接雨水;

/**
 * createTime: 2025/5/26 0:01
 * description:
 *
 * @author AirMan
 */
public class Solution3 {
    public int trap(int[] height) {
        // 双指针的优化。也可以理解为DP优化
        // 优化点：我们只需要记录前一个状态的最值
        // dp1[i] dp2[i] 的含义分别是左边最值和右边最值
        // 初始化dp：从左想由遍历，左边最值依赖前一个元素的状态，所以 leftMax = height[0]
        //          右边的最值依赖于右边元素的状态，所以我们需要分别更新这个状态
        // 注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。
        // 由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组
        // 维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。
        // 当两个指针没有相遇时，进行如下操作：
        // 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；
        // 如果 height[left]<height[right]，则必有 leftMax<rightMax，下标 left 处能接的雨水量等于 leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；
        // 如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下标 right 处能接的雨水量等于 rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。
        // 当两个指针相遇时，即可得到能接的雨水总量


        // 不用担心索引为0的地方能接水，因为此时左边最大值就是自己，相减之后任然为0，还是存放不了水
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int result = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                result += leftMax - height[left];
                left++;
            } else {
                result += rightMax - height[right];
                right--;
            }
        }
        return result;
    }
}
